#include "stdafx.h"
#include "rsa.h"

vector_int operator*(const vector_int& l, const ulong r)
{
	vector_int ret(l.size() + 1, 0);
	ulong carray = 0;
	ret.clear();
	for (int i = 0; i < l.size(); i++)
	{
		ulong tmp = l[i] * r + carray;
		ret.push_back(tmp & 0xffffffff);
		carray = tmp >> 32;
	}
	if (carray > 0)
		ret.push_back(carray);

	return ret;
}

// a*x + b*y = 1
__int64 gcdEx(__int64 a, __int64 b, __int64 *x, __int64 *y)
{
	if (b == 0)
	{
		*x = 1, *y = 0;
		return a;
	}
	else
	{
		__int64 r = gcdEx(b, a%b, x, y);
		__int64 t = *x;
		*x = *y;
		*y = t - a / b * *y;
		return r;
	}
}

ulong calc_m(ulong r, ulong N0)
{
	__int64 x, y;
	gcdEx(N0, r, &x, &y);
	if (x < 0)
	{
		x = x + r * ( -x / r + 1);
	}
	ulong N_ = x % r;
	return r - N_;
}

vector_int multi_A_B_minus_k(const vector_int& A, const vector_int& B, const vector_int& N, ulong m)
{
	vector_int C(1, 0);
	for (int i = 0; i < A.size(); i++)
	{
		ulong q = (C[0] + A[i] * B[0]) * m % mask;
		C = C + B * A[i] + N * q;
		//assert(C[0] == 0);
		C.erase(C.begin());  // C = C >> 32
		if (C > N)
			C = C - N;
		//assert(N > C);
	}
	return C;
}

ulong add4(ulong a, ulong b, ulong c, ulong d, ulong& carray)
{
	carray = 0;
	a += b;
	if (a < b)
		carray++;
	a += c;
	if (a < c)
		carray++;
	a += d;
	if (a < d)
		carray++;
	carray <<= 32;
	carray |= a >> 32;
	return a & 0xffffffff;
}

inline ulong get_value(const vector_int& array, int idx)
{
	if (idx < array.size())
		return array[idx];
	else
		return 0;
}

inline void set_value(vector_int& array, int idx, ulong val)
{
	if (idx < array.size())
		array[idx] = val;
	else
		array.push_back(val);
}

vector_int multi_A_B_minus_k_opt(const vector_int& A, const vector_int& B, const vector_int& N, ulong m)
{
	vector_int C(N.size(), 0);
	for (int i = 0; i < A.size(); i++)
	{
		ulong q = (C[0] + A[i] * B[0]) * m % mask;
		ulong carray = 0;
		add4(C[0], A[i] * B[0], N[0] * q, 0, carray);
		int j;
		for (j = 1; j < N.size(); j++)
		{
			ulong v = add4(get_value(C, j), A[i] * get_value(B, j), N[j] * q, carray, carray);
			set_value(C, j - 1, v);
		}
		if (carray != 0)
		{
			set_value(C, j - 1, carray % mask);
			carray >>= 32;
			if (carray)
				set_value(C, j, carray);

			if (C > N)
			{
				C = C - N;
			}
		}
	}
	return C;
}

int get_highest_bit_num(const vector_int& v)
{
	ulong last = v[v.size() - 1];
	int count;
	for (count = 31; count >= 0; count--)
	{
		if (last & (1 << count))
			break;
	}
	assert(count >= 0);
	count += (v.size() - 1) * 32;
	return count;
}

inline vector_int construct_RR(int k)
{
	vector_int ret(2*k + 1, 0);
	ret[2*k] = 1;
	return ret;
}

vector_int calc_rsa_3(const vector_int& n, vector_int e, vector_int input)
{
	ulong m = calc_m(mask, n[0]);
	int k = input.size();
	vector_int RR = construct_RR(k) % n;
	vector_int AR = multi_A_B_minus_k_opt(input, RR, n, m);
	vector_int X = AR;
	int highBit = get_highest_bit_num(e) - 1;
	while (highBit >= 0)
	{
		X = multi_A_B_minus_k_opt(X, X, n, m);
		if (bit_value(e, highBit))
		{
			X = multi_A_B_minus_k_opt(X, AR, n, m);
		}
		highBit--;
	}
	return multi_A_B_minus_k_opt(X, vector_int(1, 1), n, m);
}
